package algorithms.sorting.impl;

import dataStructures.IHeap;
import dataStructures.impl.MaxHeap;
import algorithms.sorting.ISort;

/**
 *
 * @author Vikas Bahirwani
 */
public class HeapSort implements ISort {

	/* (non-Javadoc)
	 * @see algorithms.sorting.ISort#sort(int[])
	 */
	@Override
	public int[] sort(int[] elements) {
		if (elements == null || elements.length <=1){
			return elements;
		}
		
		IHeap maxHeap = new MaxHeap(elements);
		elements = maxHeap.buildHeap();
		
		for(int i=(elements.length-1);i>=1;i--){
			int temp = elements[0];
			elements[0]=elements[i];
			elements[i]=temp;
			maxHeap.setHeapSize(maxHeap.getHeapSize()-1);
			maxHeap.heapify(0);
		}
		
		return elements;
	}
	

	public static void main(String[] args) {
		int a[] ={2,1,3,-4,-5,-1,7,60};
		
		ISort heapSort = new HeapSort();
		int[] c = heapSort.sort(a);
		for (int i : c) {
			
			System.out.println(i);
		}
		
	}

}
